package com.zzz.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author zizan
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 7, 4, 2, 7, 3, 1, 9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    /*
     * 堆排序
     * 最大堆方式：
     * 从结尾开始遍历，比如下标为i，那么和父节点比较 父节点下标为 (i+1)/2 - 1  如果下标从1开始就无需加1减一，直接 i / 2
     * 如果父节点比自己小，那么把自己和父节点交换，直到当前节点为根节点 i == 0
     *
     * 最小堆同上，但跟父节点想比是比自己大就交换，把小的换上去
     * 最小堆的index 不好映射啊
     */
    public static void sort(int[] array) {
        for (int i = array.length; i >= 1; i--) {
            maxHeap(array, i);
        }
    }

    public static void maxHeap(int[] array, int n) {
        int temp;
        for (int i = n - 1; i > 0; i--) {
            if (array[((i + 1) / 2) - 1] < array[i]) {
                temp = array[i];
                array[i] = array[(i + 1) / 2 - 1];
                array[(i + 1) / 2 - 1] = temp;
            }
        }
        temp = array[0];
        array[0] = array[n - 1];
        array[n - 1] = temp;
    }
}
